/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/ugly-number-ii
   @Language: C++
   @Datetime: 16-02-09 08:41
   */

// Method 1, DP, Time 17ms
class Solution {
public:
	/*
	 * @param n an integer
	 * @return the nth prime number as description.
	 * Tip: record last ugly * prime(2,3,5) > current ugly,
	 *      record all pair<last ugly, prime>. (this problem has 3 pairs)
	 * eg.  last ugly is 1, current ugly is 2.
	 *      then i2=0, i3=0, i5=0, dp[0]=1.
	 *      the next ugly candidates are dp[i2]*2, dp[i3]*3, dp[i5]*5.
	 *      find next ugly and update pairs, i2=1.
	 */
	int nthUglyNumber(int n) {
		// write your code here
		vector<long> vs(n,1);
		long i2=0, i3=0, i5=0;
		for(int i=1; i<n; ++i){
			long n2 = vs[i2]*2;
			long n3 = vs[i3]*3;
			long n5 = vs[i5]*5;
			long ugly = min(n2,min(n3,n5));
			if (ugly==n2) ++i2;
			if (ugly==n3) ++i3;
			if (ugly==n5) ++i5;
			vs[i] = ugly;
		}
		return vs[n-1];
	}
};

// Method 2, Heap, Time 26ms
class Solution {
public:
	/*
	 * @param n an integer
	 * @return the nth prime number as description.
	 */
	int nthUglyNumber(int n) {
		// write your code here
		priority_queue<long,vector<long>,greater<long> > minh;
		minh.push(1);
		for(int i=1; i<n; ++i){
			long ugly = minh.top();
			minh.pop();
			if(ugly%2==0) minh.push(ugly*2);
			else if (ugly%3==0){
				minh.push(ugly*2);
				minh.push(ugly*3);
			}
			else{
				minh.push(ugly*2);
				minh.push(ugly*3);
				minh.push(ugly*5);
			}
		}
		return minh.top();
	}
};
